翻訳と辞書 Words near each other ・ Fustius s-forma ・ Fustius sensora ・ Fusion Orchestra ・ Fusion Party ・ Fusion power ・ Fusion Power Associates ・ Fusion protein ・ Fusion Records ・ Fusion rocket ・ Fusion rules ・ Fusion splicing ・ Fusion Systems ・ Fusion Technology Center ・ Fusion torch ・ Fusion transcript ・ Fusion tree ・ Fusion welding ・ Fusion – Live in London ・ Fusion – Sarvodaya ICT4D Movement ・ Fusion! Wes Montgomery with Strings ・ Fusion-io ・ Fusion-io NVMFS ・ Fusion3 ・ Fusiona ・ Fusional language ・ Fusional vergence ・ FusionArts Museum ・ FusionCharts ・ FusionDebug ・ FusionForge Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fusion tree ： ウィキペディア英語版 Fusion tree A fusion tree is a type of tree data structure that implements an associative array on ''w''-bit integers. It uses ''O''(''n'') space and performs searches in ''O''(log''w'' ''n'') time, which is asymptotically faster than a traditional self-balancing binary search tree, and actually better than the van Emde Boas tree when ''w'' is large. It achieves this speed by exploiting certain constant-time operations that can be done on a machine word. Fusion trees were invented in 1990 by Michael Fredman and Dan Willard.〔M. L. Fredman and D. E. Willard. BLASTING through the information theoretic barrier with FUSION TREES. Proceedings of the twenty-second annual ACM symposium on Theory of Computing, 1-7, 1990.〕 Several advances have been made since Fredman and Willard's original 1990 paper. In 1999 〔A. Andersson, P. B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science, 215:337-344, 1999.〕 it was shown how to implement fusion trees under the AC0 model, in which multiplication no longer takes constant time. A dynamic version of fusion trees using Hash tables was proposed in 1996 〔R. Raman. Priority queues: Small, monotone, and trans-dichotomous. Algorithms - ESA ’96, 121-137, 1996.〕 which matched the ''O''(log''w'' ''n'') runtime in expectation. Another dynamic version using Exponential tree was proposed in 2007 〔A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. Journal of the ACM, 54:3:13, 2007.〕 which yields worst-case runtimes of ''O''(log''w'' ''n'' + log log ''u'') per operation, where ''u'' is the size of the largest key. It remains open whether dynamic fusion trees can achieve ''O''(log''w'' ''n'') per operation with high probability. == How it works == A fusion tree is essentially a B-tree with branching factor of ''w''1/5 (any small exponent is also possible), which gives it a height of ''O''(log''w'' ''n''). To achieve the desired runtimes for updates and queries, the fusion tree must be able to search a node containing up to ''w''1/5 keys in constant time. This is done by compressing ("sketching") the keys so that all can fit into one machine word, which in turn allows comparisons to be done in parallel. The rest of this article will describe the operation of a static Fusion Tree; that is, only queries are supported. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fusion tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.